package Hot100.leetcode.editor.cn.code.数组;
//Java：轮转数组
public class RotateArray{
    public static void main(String[] args) {
        Solution solution = new RotateArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    //这里假设 0≤k<n，对于 k≥n 的情况，可以转换成 0≤k<n 的情况（证明见后文）。
    //
    //设 nums=A+B，其中 A 是 nums 的前 n−k 个数，B 是后 k 个数。在上例中，A=[1,2,3,4]，B=[5,6,7]。
    //
    //题目要求把 A+B 变成 B+A，这可以用三次反转实现：
    //
    //把 nums 反转，我们得到了 rev(B)+rev(A)，其中 rev(A) 表示数组 A 反转后的结果。在上例中，rev(B)+rev(A)=[7,6,5]+[4,3,2,1]。
    //单独反转 rev(B)，因为一个数组反转两次是不变的，所以 rev(rev(B))=B，我们得到了 B。
    //单独反转 rev(A)，得到 A。
    //现在数组变成 B+A。在上例中，B+A=[5,6,7]+[1,2,3,4]，这正是我们想要的结果。

    //特殊情况
    //对于 k≥n 的情况，由于轮转 n 次等同于没有轮转，轮转 n+1 等同于轮转 1 次……
    // 依此类推，轮转 k 次等同于轮转 kmodn 次。由于 0≤kmodn≤n−1，所以 k≥n 的情况也是正确的。

    //对于任意非负整数 k，按照图中三次反转的方法，可以把下标 i 的元素移动到下标 (i+k)mod n 上。其中 n 是 nums 的长度。
class Solution {
    public void rotate(int[] nums, int k) {
        //局部翻转
        int n = nums.length;
        //对于 k≥n 的情况
        k %= n;
        reverse(nums, 0, n-1);
        reverse(nums,0, k-1);
        reverse(nums,k, n-1);
    }
    private  void reverse(int[] nums, int i, int j){
        while (i < j){
            int temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}